package day10;

//题目链接：https://www.nowcoder.com/questionTerminal/b4525d1d84934cf280439aeecc36f4af
public class 最长回文子串 {
	//中心扩散算法： 时间(O(n^2))  空间：(O(1))
	//动态规划： 时间and空间复杂度：（O(n^2)）
	public int getLongestPalindrome2 (String A) {
		//ababc   =>   3,5
		char[] s=A.toCharArray();
		int n=s.length,l,r;
		int ret=0;
		for(int i=0;i<n;i++) {
			//枚举子串为奇数的情况
			l=i-1;r=i+1;
			//一直往外扩，直到无法再扩
			while(l>=0&&r<n&&s[l]==s[r]) {
				l--;
				r++;
			}
			ret=Math.max(ret, r-l-1);
			//枚举子串为偶数的情况
			l=i;r=i+1;
			//一直往外扩，直到无法再扩
			while(l>=0&&r<n&&s[l]==s[r]) {
				l--;
				r++;
			}
			ret=Math.max(ret, r-l-1);
			
		}
		return ret;
	}
	
	
	public int getLongestPalindrome1 (String A) {
        // write code here
        char[] s=A.toCharArray();
        int n=s.length;
        boolean[][] dp=new boolean[n][n];
        //1.dp[i][j]: 区间为[i,j]的子串是否为回文串
        //2.状态转移方程：
        //   s[i]!=s[j],false
        //   s[i]==s[j], 1.i==j || i+1==j =>true
        //               2.i+1<j  => dp[i+1][j-1]
        //3.填表顺序： 从下往上，从左往右
        int ret=0;
        dp[n-1][n-1]=true;
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s[i]==s[j]){
                    if(i==j||i+1==j) 
                        dp[i][j]=true;
                    else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                    if(dp[i][j]==true){
                        ret=Math.max(ret,j-i+1);
                    }
                }
            }
        }
        return ret;
    }
}
